package algorithm;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,5,5,5,5,6,7,8,9,10};
        List<Integer> list = binarySearch(arr, 0, arr.length - 1, 5);
        System.out.println(list);
    }

    public static ArrayList<Integer> binarySearch(int[] arr,int left,int right,int findVal){
        int mid=(left+right)/2;
        int midVal=arr[mid];
        if(left>right){
            return new ArrayList<>();
        }
        if(findVal>midVal){
            return binarySearch(arr,mid+1,right,findVal);
        }else if(findVal<midVal){
            return binarySearch(arr,left,mid-1,findVal);
        }else {
            ArrayList<Integer> integers = new ArrayList<>();
            int temp=mid-1;
            while (true){
                if(temp<0 || arr[temp]!=findVal){
                    break;
                }
                integers.add(arr[temp]);
                temp--;
            }

            integers.add(arr[mid]);
            temp=mid+1;
            while (true){
                if(temp>arr.length-1 || arr[temp]!=findVal){
                    break;
                }
                integers.add(arr[temp]);
                temp++;
            }
            return integers;
        }

    }
}
